package com.example.demo.huawei;

//给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
//
//如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
//
//
//
//示例 1：
//
//输入：nums = [1,1,4,2,3], x = 5
//输出：2
//解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
//示例 2：
//
//输入：nums = [5,6,7,8,9], x = 4
//输出：-1
//示例 3：
//
//输入：nums = [3,2,20,1,1,3], x = 10
//输出：5
//解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

/**
 * 正难则反，正常情况下是在左边选一个区间，右边选一个区间，让这两个区间的和等于x，就可以满足。
 * 但是正面作战不利，我们可以反过来，在中间部分找一个连续的区间，使他们和为sum-x也行。(这里的sum是整个数组的和)。
 * 题目还要求操作次数最短，即找的两边的区间长度需要最短，那换言之就是使中间的区间长度最长即可。
 * <p>
 * 转化为：求最长子数组的长度，和为sum-x
 */
public class Main16 {
    //输入：nums = [1,1,4,2,3], x = 5
    //输出：2
    // 3, 2, 20, 1, 1, 3
    public int minOperations(int[] arr, int x) {
        int summed = sum(arr); //11
        int left = 0;
        int sum = 0;
        int maxLength = -1;
        // 1 4 4 target=4
        for (int right = 0; right < arr.length; right++) {
            sum = sum + arr[right];// 1
            while (sum > summed - x && left < arr.length) {
                sum -= arr[left];
                left++;
            }
            if (sum == summed - x) {
                maxLength = Math.max(maxLength, right - left + 1);
            }
        }
        if (maxLength == -1) {
            return -1;
        }
        return arr.length - maxLength;
    }

    private int sum(int[] arr) {
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        return sum;
    }

    public static void main(String[] args) {
        int nums[] = {1, 1, 4, 2, 3};
        int nums2[] = {5, 6, 7, 8, 9};
        int nums3[] = {3, 2, 20, 1, 1, 3};
        int nums4[] = {1, 1};
        int nums5[] = {1241, 8769, 9151, 3211, 2314, 8007, 3713, 5835, 2176, 8227, 5251, 9229, 904, 1899, 5513, 7878, 8663, 3804, 2685, 3501, 1204, 9742, 2578, 8849, 1120, 4687, 5902, 9929, 6769, 8171, 5150, 1343, 9619, 3973, 3273, 6427, 47, 8701, 2741, 7402, 1412, 2223, 8152, 805, 6726, 9128, 2794, 7137, 6725, 4279, 7200, 5582, 9583, 7443, 6573, 7221, 1423, 4859, 2608, 3772, 7437, 2581, 975, 3893, 9172, 3, 3113, 2978, 9300, 6029, 4958, 229, 4630, 653, 1421, 5512, 5392, 7287, 8643, 4495, 2640, 8047, 7268, 3878, 6010, 8070, 7560, 8931, 76, 6502, 5952, 4871, 5986, 4935, 3015, 8263, 7497, 8153, 384, 1136};
//        System.out.println(new Main16().minOperations(nums, 5));
//        System.out.println(new Main16().minOperations(nums2, 4));
        System.out.println(new Main16().minOperations(nums5, 894887480));
    }
}
